package hot;

import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.Map;

public class yisiliu {
    //    https://leetcode.cn/problems/lru-cache/?envType=study-plan-v2&envId=top-100-liked
    class LRUCache {
        //手动循环循环双向链表
        class Node {
            public int key;
            public int val;
            public Node next;
            public Node prev;

            public Node(int k, int v) {
                this.key = k;
                this.val = v;
            }
        }

        //cache里面的key和Node里面的key值相同
        public Map<Integer, Node> cache = new HashMap<>();
        //引入虚拟头节点（本质上就是哨兵节点）
        //方便边界处理和对链表的操作
        Node newHead = new Node(0, 0);
        public int capacity;

        public LRUCache(int capacity) {
            this.capacity = capacity;
            //创建循环双向链表
            //在第一次进行头插的时候（在哨兵节点后的头插） 会形成循环双向链表
            newHead.next = newHead;
            newHead.prev = newHead;
        }

        public int get(int key) {
            //先把书移到至最上面
            //getNode 是将key对应的节点 移动至链表的头部（哨兵节点后的第一个节点）
            Node node = getNode(key);
            return node == null ? -1 : node.val;

        }

        public void put(int key, int value) {
            //先把书移到至最上面
            Node node = getNode(key);
            if (node != null) {
                node.val = value;
                return;
            }
            //创建新节点
            Node newnode = new Node(key, value);
            cache.put(key, newnode);
            //将该节点移动至链表头部
            pushFront(newnode);
            if (cache.size() > capacity) {
                Node oldestnode = newHead.prev;
                //删掉对应cache里面的key
                cache.remove(oldestnode.key);
                //去掉最下面的一本书
                remove(oldestnode);
            }

        }

        public Node getNode(int key) {
            if (!cache.containsKey(key)) {
                return null;
            }
            Node node = cache.get(key);
            remove(node);
            //删除了这个节点，为什么不考虑删除cache里面的key
            //不用删除，因为pushFront又把node放到链表头部了 node的key没变化
            pushFront(node);
            return node;
        }

        public void remove(Node node) {
            node.prev.next = node.next;
            node.next.prev = node.prev;
        }

        public void pushFront(Node node) {
            node.next = newHead.next;
            node.prev = newHead;
            newHead.next = node;
            node.next.prev = node;
        }

    }
}



